Часто в задачах встречается следующая конструкция - есть дома
и дороги, их соединяющие; у каждой дороги есть длина. По другой
терминологии такая конструкция называется графом, дома называются
"вершинами", дороги - "ребрами" или "дугами", а длина дороги -
"весом ребра" или "весом дуги". Таким образом фраза 'Найти мини-
мальный вес пути между вершинами s и k в графе' может быть переве-
дена так: 'Есть дома и дороги их соединяющие. Также заданы длины
дорог. Найти кратчайшую длину пути от города s до города k, если
двигаться можно только по дорогам'. Пропускная способность дуги
(i,j) означает, например, сколько груза может быть перевезено по
дороге (по дуге) (i,j) за единицу времени); а поток по дуге (i,j)
- это сколько перевозится сейчас на самом деле).
Часто используют следующие обозначения: Г(x(i))- множество
вершин, в которые есть дуга из вершины i; Д(x(i))- множество вер-
шин, из которых есть дуга в вершину i.
Пусть в графе N вершин. Длины дуг обычно заносятся в матрицу (назовем ее C) размера N
на N, называемой матрицей смежности:
var С: array [1..N,1..N] of integer;
Элемент C[i,j] этой матрицы равен длине дуги (дороги>), сое-
диняющей вершины i и j, и равен (например) 0 или -1, если такой
дуги нет. Если дорога двунаправленная (дуга неориентированная), то
очевидно, что C[i,j]=C[j,i].